#include <vector>

using namespace std;

int rob(vector<int> &nums)
{
    int n = nums.size();
    if(n == 1)
    {
        return nums[0];
    }
    vector<int> dp(n,0);     //dp[i]存储第i步的最高金额
    dp[0] = nums[0];
    dp[1] = max(nums[0],nums[1]);

    for(int i = 2;i < n;i++)
    {
        dp[i] = max(dp[i - 1],nums[i] + dp[i - 2]); //选择当前房子偷，或者不偷当前房子。
    }
    return dp[n - 1];
}